package mkpsolving;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by Julien on 09/04/14.
 */

// Cette classe représente un noeud de notre arbre de décision qu'il soit solution ou non
//Un noeud a une evaluation (optimum) une liste de contraintes (les décisions prises dans le parcours de l'arbre ex: X1=0 X2=1 X3= 0 ...)
// la liste des objets séléctionnés (valeurs entières ou non)
public class NodeMkp{
    private double eval;
    // Tout noeud est considéré comme solution avant que l'on évalue son optimum
    private boolean solution = true;
    private Map<Integer, Double> constraints = new HashMap<Integer, Double>();
    private List<Double> choix;
    //Tout noeud ne peut pas être branché tant qu'on a pas évalué son optimum
    private int possibleBranch = -1;

    //Constructeur du noeud racine
    NodeMkp(double eval, List<Double> choix) {
        this.eval = eval;
        this.choix = choix;
    }

    //Constructeur de noeud fils (soit fils gauche soit fils droit) en fonction du booléen passée en paramètre
    NodeMkp(NodeMkp nodeMkp, boolean leftSon) {
        constraints.clear();
        constraints.putAll(nodeMkp.getConstraints());
        if (leftSon) {
            this.constraints.put(nodeMkp.getPossibleBranch(), 0.0);
        } else {
            this.constraints.put(nodeMkp.getPossibleBranch(), 1.0);
        }
        choix = new ArrayList<Double>();
        eval = 0;
    }

    //Constructeur par défaut
    public NodeMkp() {
        eval = -1;
    }

    /**Cette fonction évalue si un noeud peut être branché ou non (solution entière ou non)*/
    public void evaluateBranching() {
        for (int i = 0; i < choix.size(); i++) {
            if (choix.get(i) != 1.0 && choix.get(i) != 0.0) {
                possibleBranch = i;
            }
        }
    }

    // Cette fonction permet de trouver l'optimum du noeud en fonction du sac et de la liste des objets restants
    //Cette fonction est très proche de la fonction getUpperBound de la classe Mkp
    public void findOptimum(Sac s, List<Objet> objetList) {
        choix.clear();
        double optimum = 0;
        double limit = s.getvolume();
        for (int i = 0; i < objetList.size(); i++) {
            choix.add(0.0);
            if (this.constraints.containsKey(i)) {
                choix.set(i, this.constraints.get(i));
                if (constraints.get(i) == 1.0) {
                    limit -= objetList.get(i).getpoids();
                    optimum += objetList.get(i).getUtil();
                }
            }
        }
        if (limit > 0) {
            for (int i = 0; i < objetList.size(); i++) {
                if (!this.constraints.containsKey(i)) {
                    if (limit > objetList.get(i).getpoids()) {
                        optimum += objetList.get(i).getUtil();
                        choix.set(i, 1.0);
                        limit -= objetList.get(i).getpoids();
                    } else if (limit > 0) {
                        solution = false;
                        optimum += (limit) * objetList.get(i).getRapportPU();
                        choix.set(i, limit / objetList.get(i).getpoids());
                        limit = 0;
                    }
                }
            }
            if (optimum != 0) {
                eval = optimum;
            } else {
                eval = -1;
            }
        } else {
            eval = -1;
        }
    }


    public double getEval() {
        return eval;
    }

    public Map<Integer, Double> getConstraints() {
        return constraints;
    }

    public List<Double> getChoix() {
        return choix;
    }

    public int getPossibleBranch() {
        return possibleBranch;
    }

    public boolean isSolution() {
        return solution;
    }
}
